|
Cristian's Algorithm (introduced by Flaviu Cristian in 1989) is a method for clock synchronization which can be used in many fields of distributive computer science but is primarily used in low-latency intranets. Cristian observed that this simple algorithm is probabilistic, in that it only achieves synchronization if the round-trip time (RTT) of the request is short compared to required accuracy. It also suffers in implementations using a single server, making it unsuitable for many distributive applications where redundancy may be crucial. == The algorithm == Cristian's Algorithm works between a process P, and a time server S — connected to a source of UTC (Coordinated Universal Time). Put simply: # P requests the time from S # After receiving the request from P, S prepares a response and appends the time T from its own clock. # P then sets its time to be T + RTT/2 This method assumes that the RTT is split equally between request and response, which may not always be the case but is a reasonable assumption on a LAN connection. Further accuracy can be gained by making multiple requests to S and using the response with the shortest RTT. We can estimate the accuracy of the system as follows. Let ''min'' be the minimum time to transmit a message one-way. The earliest point at which S could have placed the time T, was ''min'' after P sent its request. Therefore, the time at S, when the message by P is received, is in the range (T + ''min'') to (T + RTT - ''min''). The width of this range is (RTT - 2 *''min''). This gives an accuracy of (RTT/2 - ''min''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cristian's algorithm」の詳細全文を読む スポンサード リンク
|